#include "headfiles.h"

using namespace std;

CalcMedian::CalcMedian() {
    max_heap_capacity = 100;
    max_heap_size = 0;
    max_heap = (int *) malloc(sizeof(int) * max_heap_capacity);

    min_heap_capacity = 100;
    min_heap_size = 0;
    min_heap = (int *) malloc(sizeof(int) * max_heap_capacity);
}

CalcMedian::~CalcMedian() {
    free(max_heap);
    max_heap_capacity = 0;
    max_heap_size = 0;

    free(min_heap);
    min_heap_capacity = 0;
    min_heap_size = 0;
}

bool CalcMedian::addElemMaxHeap(int elem) {
    if (max_heap_size >= max_heap_capacity) {
        int *tmp = (int *)malloc(sizeof(int) * max_heap_capacity * 2);
        memcpy(tmp, max_heap, sizeof(int) * max_heap_capacity);
        free(max_heap);
        max_heap = tmp;
        max_heap_capacity *= 2;
    }

    max_heap[max_heap_size] = elem;
    int child = max_heap_size;
    int parent;
    ++max_heap_size;

    parent = (child - 1) / 2;
    while (parent >= 0) {
        if (max_heap[parent] < max_heap[child]) {
            int tmp_val = max_heap[parent];
            max_heap[parent] = max_heap[child];
            max_heap[child] = tmp_val;

            if (parent <= 0) {
                break;
            }

            child = parent;
            parent = (child - 1) / 2;
        }
        else {
            break;
        }
    }

    return true;
}

bool CalcMedian::addElemMinHeap(int elem) {
    if (min_heap_size >= min_heap_capacity) {
        int *tmp = (int *)malloc(sizeof(int) * min_heap_capacity * 2);
        memcpy(tmp, min_heap, sizeof(int) * min_heap_capacity);
        free(min_heap);
        min_heap = tmp;
        min_heap_capacity *= 2;
    }

    min_heap[min_heap_size] = elem;
    int child = min_heap_size;
    int parent;
    ++min_heap_size;

    parent = (child - 1) / 2;
    while (parent >= 0) {
        if (min_heap[parent] > min_heap[child]) {
            int tmp_val = min_heap[parent];
            min_heap[parent] = min_heap[child];
            min_heap[child] = tmp_val;

            if (parent <= 0) {
                break;
            }

            child = parent;
            parent = (child - 1) / 2;
        }
        else {
            break;
        }
    }

    return true;

}

int CalcMedian::getRootMaxHeap() {
    if (max_heap_size <= 0) {
        cout << "Error, empty max heap" << endl;
        return -1;
    }

    int ret_val = max_heap[0];

    // Move the last element to loc 0
    max_heap[0] = max_heap[max_heap_size - 1];
    --max_heap_size;
    
    // Reshape the max heap
    int p, l_child, r_child, c_child;
    p = 0;
    while (p < max_heap_size) {
        l_child = 2 * p + 1;
        r_child = 2 * p + 2;

        c_child = -1;
        if (l_child < max_heap_size && 
            max_heap[p] < max_heap[l_child]) {
            c_child = l_child;
        }

        if (r_child < max_heap_size && 
            max_heap[p] < max_heap[r_child]) {
            if (max_heap[l_child] < max_heap[r_child]) {
                c_child = r_child;
            }
        }

        if (c_child == -1) {
            break;
        }
        else {
            int tmp_val = max_heap[c_child];
            max_heap[c_child] = max_heap[p];
            max_heap[p] = tmp_val;

            p = c_child;
        }
    }

    return ret_val;
}

int CalcMedian::getRootMinHeap() {
    if (min_heap_size <= 0) {
        cout << "Error, empty max heap" << endl;
        return -1;
    }

    int ret_val = min_heap[0];

    // Move the last element to loc 0
    min_heap[0] = min_heap[min_heap_size - 1];
    --min_heap_size;
    
    // Reshape the max heap
    int p, l_child, r_child, c_child;
    p = 0;
    while (p < min_heap_size) {
        l_child = 2 * p + 1;
        r_child = 2 * p + 2;

        c_child = -1;
        if (l_child < min_heap_size && 
            min_heap[p] > min_heap[l_child]) {
            c_child = l_child;
        }

        if (r_child < min_heap_size && 
            min_heap[p] > min_heap[r_child]) {
            if (min_heap[l_child] > min_heap[r_child]) {
                c_child = r_child;
            }
        }

        if (c_child == -1) {
            break;
        }
        else {
            int tmp_val = min_heap[c_child];
            min_heap[c_child] = min_heap[p];
            min_heap[p] = tmp_val;

            p = c_child;
        }
    }

    return ret_val;
}

int CalcMedian::getMedian(int elem) {
    if (min_heap_size == 0) {
        addElemMinHeap(elem);
    } 
    else {
        if (elem >= min_heap[0]) {
            addElemMinHeap(elem);
        }
        else {
            addElemMaxHeap(elem);
        }
    }

    // If elem num in the min heap is 2 or more than that in 
    // the max heap, move the root of the min heap to the 
    // max heap
    if (min_heap_size - max_heap_size > 1) {
        int tmp_val = getRootMinHeap();

        addElemMaxHeap(tmp_val);
    }

    if (max_heap_size - min_heap_size > 0) {
        int tmp_val = getRootMaxHeap();
        addElemMinHeap(tmp_val);
    }

    int median = min_heap[0];

    return median;
}



